\chapter{哈希函数(Hash Function)}
\section{哈希函数特点}
哈希函数(Hash function)H也称为单向散列函数，其特点是:
\begin{enumerate}
	\item 函数输入为任意长度的消息M，输出为固定长度的消息h，$h=H(M)$.
	\item 函数H是容易计算的，也就是说给定M，很容易计算$h=H(M)$.
	\item 给定h，计算M，这是个困难问题。
	\item 给定M，找到另外一个消息M'，使得$H(M)=H(M')$是个困难问题。也就是哈希函数要能抗碰撞(collision-resistance)。
\end{enumerate}


\section{对哈希函数的攻击}
\subsection{穷举攻击}
已知一个哈希值H(M)，攻击者依据一定的遍历规则创建消息，直到找到一个消息M'，使得$H(M')=H(M)$。
\subsection{生日攻击(birthday attack)}
攻击者通过一定的方法寻找两个随机消息M'和M，使得$H(M')=H(M)$.\par
这种冲突通常比较容易实现，我们下面进行解释，这也是生日攻击名字的来源。\par
生日悖论是指在不少于 23 个人中至少有两人生日相同的概率大于 50\%。例如在一个 30 人的小学班级中，存在两人生日相同的概率为 70\%。对于 60 人的大班，这种概率要大于 99\%。从引起逻辑矛盾的角度来说，生日悖论并不是一种 “悖论”。但这个数学事实十分反直觉，故称之为一个悖论。生日悖论的数学理论被应用于设计密码学攻击方法——生日攻击。\footnote{此段话摘抄自\url{https://baike.baidu.com/item/生日悖论}}\par
对于一个哈希函数，假定其输出为m位，利用穷举攻击，找到一个碰撞(collision)需要$2^m$次试探，而需要寻找两个随机消息，其发生碰撞，只需要$2^{m/2}$次试探，我们看看这两个区别。假如m=64，计算一次哈希值$1/10^6$秒(也就是说1秒计算1百万个哈希值)，那么用穷举法最多需要计算$2^{64}=18446744073709551616$次，大约需要58万年，如果我们只是寻找两个一样的数，需要计算$2^{32}=4294967296$次，大约需要1个多小时。\par
从上面的例子可以看到，如果你认为哈希值长度为m位是就够了，如果你需要考虑生日攻击，那么你选择的哈希函数生成的哈希值长度应该是2m。\par
例如如果你想让攻击者破解哈希函数的可能性低于$1/2^{80}$，那么你应该选择使用160位的哈希函数。

\newpage

\section{MD5(Message-Digest algorithm 5)}
MD5是Ron Rivest在1990年10月作为RFC提出的(RFC 1321)，其前身是MD4(RFC 1320)。MD5输入为任意长度的信息，输出128bit的摘要信息(散列值)。

\subsection{MD5算法}

\subsubsection{消息填充}
填充后的消息比特长度L为模512下是448，也就是说$L \equiv 448\ (mod\ 512)$，或者说$L=n\times 512 +448$，n为大于等于1的正整数。填充方式为第一位为1，后面为0.

\subsubsection{附加消息长度}
前面填充后最后有448bit，448+64=512bit，留下的这64bit用于填写附加消息长度，用little-endian方式存储。那么可存储的最大附加消息长度为$2^{64}$，如果消息长度大于此数，存储长度模$2^{64}$后的值。\par

附加消息长度后，进行后续运算的消息长度是512的倍数。

\subsubsection{缓冲区初始化}
就是初始化MD5核心算法中的$W_0,X_0,Y_0,Z_0$，$W_0=01\ 23\ 45\ 67;X_0=89\ AB\ CD\ EF;Y_0=FE\ DC\ BA\ 98;Z_0=76\ 54\ 32\ 10$。

\subsubsection{分组流水处理}
将消息分为n个512bit长度的分组$m_1,m_2,\ldots,m_n$，然后对n个分组依次执行：
\begin{enumerate}
	\item $(W_1,X_1,Y_1,Z_1)=H_{MD5}(W_0,X_0,Y_0,Z_0,m_1)$
	\item $(W_2,X_2,Y_2,Z_2)=H_{MD5}(W_1,X_1,Y_1,Z_1,m_2)$
	\item $(W_3,X_3,Y_3,Z_3)=H_{MD5}(W_2,X_2,Y_2,Z_2,m_3)$ \par
	\ldots
	\item[n.] $(W_{n},X_{n},Y_{n},Z_{n})=H_{MD5}(W_{n-1},X_{n-1},Y_{n-1},Z_{n-1},m_n)$
\end{enumerate}


\subsubsection{输出}
MD5的输出为$W_{n} || X_{n} || Y_{n} || Z_{n}$。

\subsubsection{MD5算法表示}
整个MD5算法，输入为原始消息$M_s$，初始量$W_0,X_0,Y_0,Z_0$，输出为128bit，$W || X || Y || Z$，我们记为$(W,X,Y,Z) \ or\ W || X || Y || Z =MD5(W_0,X_0,Y_0,Z_0,M_s)$.


\subsection{核心算法$H_{MD5}$}
核心算法$H_{MD5}$是个分组算法，输入是512位的分组数据，输出是128位。

\subsubsection{$H_{MD5}$算法}
$H_{MD5}$算法的伪代码如下：\par
\hspace{2cm} $M,W_0,X_0,Y_0,Z_0$ \par
\hspace{2cm} $(W_1,X_1,Y_1,Z_1)=R(F,G,H,I,W_0,X_0,Y_0,Z_0,M)$ \par
\hspace{2cm} $W=W_0 + W_1 \ (mod \ 2^{32}) $ \par
\hspace{2cm} $X=X_0 + X_1 \ (mod \ 2^{32}) $ \par
\hspace{2cm} $Y=Y_0 + Y_1 \ (mod \ 2^{32}) $ \par
\hspace{2cm} $Z=Z_0 + Z_1 \ (mod \ 2^{32}) $ \par
\hspace{2cm} 输出W,X,Y,X \par

上面伪代码表示的这个算法，其输入是$M,W_0,X_0,Y_0,Z_0$，算法输出是$W,X,Y,X$,用$(W,X,Y,X)=H_{MD5}(W_0,X_0,Y_0,Z_0,M)$符号化来表示。


\subsubsection{四轮运算R}
算法的输入是512bit的消息M，我们再将其分为16组，每组32bit，$M=M_0 || M_1 || M_2 || \ldots || M_{15}$,然后对其进行四轮核心运算。我们将整个四轮运算过程记为$R(F,G,H,I,W,X,Y,Z,M):W\times X \times Y \times Z \times M \rightarrow W\times X \times Y \times Z$,也就是说这四轮运算后输出是新的W,X,Y,X,下面我们看看四轮运算的具体过程\par
$\blacklozenge$ 第一轮C为F,所以核心运算是FF(W,X,Y,Z,M,s,t)，在第一轮中依次对16个分组数据执行FF运算，也就是说第一轮执行16次FF运算，每一次的执行FF时，W,X,Y,X是上一次运算后的W,X,Y,X，在执行第一次FF时，W,X,Y,X的初始值为，$W=0x01234567,X=0x89abcdef,Y=0xfedcba98,Z=0x76543210$\footnote{可以看出这4个32bit变量是0~f正序逆序排列，然后分割为四个变量所得}.我们用伪代码描述此轮算法：\par

\hspace{2cm}	W,X,Y,Z初始化 \par
\hspace{2cm}	for i=0 to 15 \par
\hspace{3cm}	  $FF(W,X,Y,Z,M^1_i,s^1_i,t_{i+1})$ \par
\hspace{3cm}	  $WXYZ=WXYZ >> 32$;表示将四个值连接，然后右循环移位32，也就是新W值为旧Z，新X值为旧W，新Y值为旧X，新Z值为旧Y \par
\vspace{1cm} 


$\blacklozenge$ 第二轮C为G：\par

\hspace{2cm}	W,X,Y,Z上一轮遗留值\par
\hspace{2cm}	for i=0 to 15\par
\hspace{3cm}	  $GG(W,X,Y,Z,M^2_i,s^2_i,t_{i+17})$\par
\hspace{3cm}	  $WXYZ=WXYZ >> 32$;表示将四个值连接，然后右循环移位32，也就是新W值为旧Z，新X值为旧W，新Y值为旧X，新Z值为旧Y\par
\vspace{1cm} 

$\blacklozenge$ 第三轮C为H：\par

\hspace{2cm}	W,X,Y,Z上一轮遗留值\par
\hspace{2cm}	for i=0 to 15\par
\hspace{3cm}	  $HH(W,X,Y,Z,M^3_i,s^3_i,t_{i+33})$\par
\hspace{3cm}	  $WXYZ=WXYZ >> 32$;表示将四个值连接，然后右循环移位32，也就是新W值为旧Z，新X值为旧W，新Y值为旧X，新Z值为旧Y\par
\vspace{1cm} 

$\blacklozenge$ 第四轮C为I：\par

\hspace{2cm}	W,X,Y,Z上一轮遗留值\par
\hspace{2cm}	for i=0 to 15\par
\hspace{3cm}	  $II(W,X,Y,Z,M^4_i,s^4_i,t_{i+49})$\par
\hspace{3cm}	  $WXYZ=WXYZ >> 32$;表示将四个值连接，然后右循环移位32，也就是新W值为旧Z，新X值为旧W，新Y值为旧X，新Z值为旧Y\par
\vspace{1cm} 


\subsubsection{R中的$M^n_i,(n=1,2,3,4)$}
四轮运算中，每轮消息顺序不同，第一轮为顺次，消息从$M_0,M_2,\ldots,M_{15}$，第二、三、四轮，对M的顺序进行了置换：\par
第一轮 $M^1_i=M_i,i=0,1,\ldots,15$\par
第二轮 $M^2_i=M_{1+5i\ mod\ 16},i=0,1,\ldots,15$\par
第三轮 $M^3_i=M_{5+3i\ mod\ 16},i=0,1,\ldots,15$\par
第四轮 $M^4_i=M_{7i\ mod\ 16},i=0,1,\ldots,15$\par
按上面公式，可知，第二轮M的顺序是：\\
$M_1,M_6,M_{11},M_0,M_5,M_{10},M_{15},M_{4},M_{9},M_{14},M_{3},M_{8},M_{13},M_{2},M_{7},M_{12}$


\subsubsection{R中的$s^n_i,(n=1,2,3,4)$}
每轮每次运算移位数$s^n_i$的取值如表\ref{MD5-S}，n表示时第几轮，i表示是本轮的第几次运算。
\begin{table}[htbp]
	\centering 
	\caption{ MD5中循环移位操作参数选择 } 
	\label{MD5-S}
	\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
		\hline 
		\diagbox{轮数}{参数}  &1  &2  &3    &4  &5  &6  &7   &8   &9  &10  &11  &12  &13  &14  &15  &16  \\ 
		\hline 
		 1                   & 7 & 12 &17  & 22 &7  &12 &17  &22  &7  &12  &17  &22  &7  &12  &17  &22  \\ 
		\hline 
		 2                   & 5 & 9 & 14 & 20  &5  &9  &14  &20  &5  &9   &14  &20  &5  &9  &14  & 20 \\ 
		\hline 
		 3                   & 4 & 11 &16  & 23 &4  &11 &16  &23  &4  &11  &16  &23  &4  &11  &16  &23  \\ 
		\hline 
		 4                   & 6 & 10 & 15 & 21 &6  &10 &15  &21  &6  &10  &15  &21  &6  &10  &15  & 21 \\ 
		\hline 
	\end{tabular} 
\end{table}

%\begin{figure}[htbp]
%	\centering
%	\includegraphics[width=0.7\textwidth]{MD5-s.png}
%	\caption{MD5中每次运算移位步数}
%	\label{MD5-shift}
%\end{figure}


\subsubsection{R中的$t_i$}
每轮中的每次运算都有$t_i$，他是个常数，在四轮运算中其是顺序变换，共有64个常数值$t_1,t_2,\ldots,t_64$，我们这样设定这个常数值,$t_i=[2^{32} \times abs(sin(i))]$,其中i的单位为弧度(RAD)，[]表示取整运算，就是取一个数的整数部分，abs是绝对值，其实我们可以事先做好这个常数表，以备计算是使用，下面我们计算$t_1$。\par
$t_1=[2^{32} \times abs(sin(1))] = [3614090360.3] =3614090360 = [d76aa478]_{16}$

\subsubsection{核心运算}
我们定义一个核心运算，其中C为非线性函数F,G,H,I中的一个，$d<<s$表示对数d循环左移s位，+表示模$2^{32}$加法，后面为了方便我们直接写+，核心运算CC我们定义为：
\begin{equation}
CC(W,X,Y,Z,M,s,t):W=X+((W+C(X,Y,Z)+M+t)<<s)
\end{equation}
\par
如果C用F替换，那么核心运算CC就是FF；如果C用G替换，那么核心运算CC就是GG；如果C用H替换，那么核心运算CC就是HH；如果C用I替换，那么核心运算CC就是II。
\par
这里我们其实是定义了R运算中的函数FF、GG、HH、II。

\subsubsection{非线性函数}
在核心运算定义中有四个非线性函数$F(X,Y,Z),G(X,Y,Z),H(X,Y,Z),I(X,Y,Z)$，下面我们分别定义这四个非线性函数。\par
我们定义四个非线性函数，其中X，Y，Z是32bit数,$\wedge$是与操作，$\vee$是或操作,$\oplus$是异或操作，$\neg$是非操作。\par
\begin{enumerate}
	\item $F(X,Y,Z)= (X \wedge Y ) \vee (\neg X \wedge Z)$
	\item $G(X,Y,Z)=(X \wedge Z ) \vee (\neg Y \wedge \neg Z)$
	\item $H(X,Y,Z)=X \oplus Y \oplus Z$
	\item $I(X,Y,Z)=Y \oplus (X \wedge \neg Z)$
\end{enumerate}

\section{MD5安全性}
这节文字摘抄自网络上\footnote{\url{https://en.bitcoinwiki.org/wiki/MD5}}。

\subsection{History and cryptanalysis}
MD5 is one in a series of message digest algorithms designed by Professor Ronald Rivest of Massachusetts Institute of Technology|MIT (Rivest, 1992). When analytic work indicated that MD5's predecessor MD4 was likely to be insecure, Rivest designed MD5 in 1991 as a secure replacement. (Hans Dobbertin did indeed later find weaknesses in MD4.) \par

In 1993, Den Boer and Bosselaers gave an early, although limited, result of finding a "pseudo-collision" of the MD5 compression function; that is, two different initialization vectors that produce an identical digest.\par

In 1996, Dobbertin announced a collision of the compression function of MD5 (Dobbertin, 1996). While this was not an attack on the full MD5 hash function, it was close enough for cryptographers to recommend switching to a replacement, such as SHA-1 or RIPEMD-160.\par

The size of the hash value (128 bits) is small enough to contemplate a birthday attac. MD5CRK was a distributed project started in March 2004 with the aim of demonstrating that MD5 is practically insecure by finding a collision using a birthday attack.\par

MD5CRK ended shortly after 17 August 2004, when collisions for the full MD5 were announced by Xiaoyun Wang, Dengguo Feng, Xuejia Lai, and Hongbo Yu. Their analytical attack was reported to take only one hour on an IBM p690 cluster.\par

On 1 March 2005, Arjen Lenstra, Xiaoyun Wang, and Benne de Weger demonstrated construction of two X.509 certificates with different public keys and the same MD5 hash value, a demonstrably practical collision. The construction included private keys for both public keys. A few days later, Vlastimil Klima described an improved algorithm, able to construct MD5 collisions in a few hours on a single notebook computer. On 18 March 2006, Klima published an algorithm that could find a collision within one minute on a single notebook computer, using a method he calls tunneling.\par

Various MD5-related RFC errata have been published. In 2009, the United States Cyber Command used an MD5 hash value of their mission statement as a part of their official emblem.\par

On 24 December 2010, Tao Xie and Dengguo Feng announced the first published single-block (512-bit) MD5 collision. (Previous collision discoveries had relied on multi-block attacks.) For "security reasons", Xie and Feng did not disclose the new attack method. They issued a challenge to the cryptographic community, offering a US\$10,000 reward to the first finder of a different 64-byte collision before 1 January 2013. Marc Stevens responded to the challenge and published colliding single-block messages as well as the construction algorithm and sources.\par

In 2011 an informational RFC 6151 was approved to update the security considerations in MD5 and HMAC-MD5.\par

\subsection{security}
The security of the MD5 hash function is severely compromised. A collision attack exists that can find collisions within seconds on a computer with a 2.6 GHz Pentium 4 processor . Further, there is also a chosen-prefix collision attack that can produce a collision for two inputs with specified prefixes within hours, using off-the-shelf computing hardware.\par

The ability to find collisions has been greatly aided by the use of off-the-shelf GPUs. On an NVIDIA GeForce 8400GS graphics processor, 16–18 million hashes per second can be computed. An NVIDIA GeForce 8800 Ultra can calculate more than 200 million hashes per second.\par

These hash and collision attacks have been demonstrated in the public in various situations, including colliding document files and digital certificates.\par

\newpage 


\section{SHA}
SHA是Secure Hash Algorithm的缩写。1993年发布SHA，1995年发布SHA-1，2002年发布SHA-2，2008年发布SHA-3，2015年发布SHA-4。
\subsection{SHA-1}
SHA-1输入为小于$2^{64}$比特长的任意消息，生成一个160比特(20字节，40个16进制值)的摘要信息。
SHA-1的介绍，我们直接节选引用NIST的标准\footnote{Federal Information Processing Standards Publication 180-1,1995 April 17,Specifications for the SECURE HASH STANDARD}，也许看的更直观一些。\par

\subsubsection{Introduction}
The Secure Hash Algorithm (SHA) is required for use wi th the Digital Signature Algori th m
(DSA) as specified in the Digital Signature Standard (DSS) and whenever a se cu re hash algorithm
is required for federal applications. For a message of length< 2 64 bits, the SHA produces a 16 0-
bit condensed representation of the message called a message digest. The message digest is used
during generation of a signature for the message. The SHA is also used to compute a message
digest for the received version of the message during the process of verifying the signature. Any
change to the message in transit will, with very high probability, result in a different message
digest, and the signature will fail to verify.\par

The SHA is designed to have the following properties: it is computationally infeasible to find a
message which corresponds to a given message digest, or to find two different messages which
produce the same message digest.

\subsubsection{BIT strings and integers}
The following terminology related to bit strings and integers will be used:\par

a. A hex digit is an element of the set { 0 , 1 , . . . , 9 , A , . . . , F} . A hex digit
is the representation of a 4-bit string. Examaples: 7 = 0111, A =1010.\par

b. A word equals a 32-bit string which may be represented as a sequence of 8 hex digits.
To convert a word to 8 hex digits each 4-bit string is converted to its hex equivalent as
described in (a) above. Example:\par
\hspace{2cm} 1010 0001 0000 0011 1111 1110 0010 0 01 1. =A103FE23
\par

c. An integer between 0 and $2^{32}-1$ inclusive may be represe nt ed as a word. The least
significant four bits of the integer are represented by the ri ght-most hex digit of the word
representation. Example: the integer $291 = 2 8 +2 5 +2 1 +2° = 256+32+ 2+1$ is represented
by the hex word, 00000123.\par
If z is an integer, $0 \leq z < 2^{64}$ , then $z = 2^{32} x + y$ where $0 \leq x < 2^{32}$ and $0\leq y < 2^{32}$. Since
x and y can be represented as words X and Y, respectively, z can be represented as the
pair of words (X,Y).\par

d. block= 512-bit string. A block (e.g., B) may be represented as a sequence of 16 words.

\subsubsection{Operations on Words}
The following logical operators will be applied to words:\par
a. Bitwise logical word operations\par
\hspace{2cm} $X \wedge Y$ = bitwise logical "and" of X and Y.\par
\hspace{2cm} $X \vee Y$ = bitwise logical "inclusive-or" of X and Y.\par
\hspace{2cm} $X \ \emph{XOR} \ Y$= bitwise logical "exclusive-or" of X and Y.\par
\hspace{2cm} $\sim X$ = bitwise logical "complement" of X.\par

b. The operation $X + Y$ is defined as follows: words $X$ and $Y$ represent integers $x$ and $y$,
where $0\leq x < 2^{32}$ and $0\leq y < 2^{32}$. For positive integers n and m, let n mod m be the
remainder upon dividing n by m. Compute
\[z = \left( x + y\right)  \pmod{2^{32}}\]
Then $0\leq z < 2^{32}$ Convert $z$ to a word, $Z$, and define $Z = X + Y$.\par

c. The circular left shift operation $S^n\left( X \right) $, where X is a word and n is an integer with $0\leq n < 32$, is defined by
\[S^n\left( X\right)  = \left( X << n\right)  \vee \left( X >> 32-n\right) .\]
In the above, X << n is obtained as follows: discard the left-most n bits of X and then
pad the result with n zeroes on the right (the result will still be 32 bits). X >> n is
obtained by discarding the right-most n bits of X and then padding the result with n zeroes on the left Thus $S^n\left( X\right) $ is equivalent to a circular shift of X by n positions to the left.

\subsubsection{Message Padding}
The SHA is used to compute a message digest for a message or data file that is provided as
input. The message or data file should be considered to be a bit string. The length of the
message is the number of bits in the message (the empty message has length 0). If the number
of bits in a message is a multiple of 8, for compactness we can represent the message in hex.
The purpose of message padding is to make the total length of a padded message a multiple of
512. The SHA sequentially processes blocks of 512 bits when computing the message digest.
The following specifies how this padding shall be performed. As a summary, a "1" followed by
m "O"s followed by a 64-bit integer are appended to the end of the message to produce a padded
message of length 512 x n. The 64-bit integer is l, the length of the original message. The
padded message is then processed by the SHA as n 512-bit blocks.\par

Suppose a message has length $l < 2^ {64}$. Before it is input to the SHA, the message is padded on
the right as follows:\par

a. "l" is appended. Example: if the original message is "01010000", this is padded to
"010100001 ".\par

b. "0"s are appended. The number of "0"s will depend on the original length of the
message. The last 64 bits of the last 512-bit block are reserved for the length $l$ of the
original message.\par
Example: Suppose the original message is the bit string\par
\hspace{2cm} 01100001 01100010 01100011 01100100 01100101.\par

After step (a) this gives\par
\hspace{2cm} 01100001 01100010 01100011 01100100 01100101 1.\par

Since $l = 40$, the number of bits in the above is 41 and 407 "0"s are appended, making
the total now 448. This gives (in hex)\par
\hspace{2cm}61626364 65800000 00000000 00000000\par
\hspace{2cm}00000000 00000000 00000000 00000000\par
\hspace{2cm}00000000 00000000 00000000 00000000\par
\hspace{2cm}00000000 00000000.
\par

c. Obtain the 2-word representation of l, the number of bits in the original message. If
$l < 2^{32}$ then the first word is all zeroes. Append these two words to the padded message.\par

Example: Suppose the original message is as in (b). Then $l = 40$ (note that l is computed
before any padding). The two-word representation of 40 is hex 00000000 00000028.
Hence the final padded message is hex\par
\hspace{2cm}61626364 65800000 00000000 00000000\par
\hspace{2cm}00000000 00000000 00000000 00000000\par
\hspace{2cm}00000000 00000000 00000000 00000000\par
\hspace{2cm}00000000 00000000 00000000 00000028.
\par
The padded message will contain 16n words for some n > 0. The padded message is regarded
as a sequence of n blocks $M_1,M_2 ,\ldots, M_n$ , where each $M_i$ contains 16 words and $M_1$ contains
the first characters (or bits) of the message.



\subsubsection{Functions Used}
A sequence of logical functions $f_0 , f_1 ,\ldots , f_{79}$ is used in the SHA. Each $f_t, 0\leq t \leq 79$, operates
on three 32-bit words and produces a 32-bit word as output. $f_t$ is defined as follows: for words,
B, C, D,
\[f_t\left( B,C,D\right)=(B \wedge C) \vee \left( \sim B \wedge D \right) ,0\leq t \leq 19 \]
\[f_t\left( B,C,D\right)=B\ \emph{XOR} \ C\ \emph{XOR} \ D  ,20\leq t \leq 39 \]
\[f_t\left( B,C,D\right)=(B \wedge C) \vee \left( B \wedge D \right) \vee \left( C \wedge D \right)  ,40\leq t \leq 59 \]
\[f_t\left( B,C,D\right)=B\ \emph{XOR} \ C\ \emph{XOR} \ D,60\leq t \leq 79 \]

\subsubsection{Constants Used}
A sequence of constant words $K_0, K_1 , \ldots , K_{79}$ is used in the SHA. In hex these are given by\par
\hspace{2cm} $K_t= 5A827999,0 \leq t \leq 19$\par
\hspace{2cm} $K_t= 6ED9EBA1,20 \leq t \leq 39$\par
\hspace{2cm} $K_t = 8FlBBCDC,40 \leq t \leq 59$\par
\hspace{2cm} $K_t= CA62C1D6,60 \leq t \leq 79$\par

\subsubsection{Computing the Message digest}
The message digest is computed using the final padded message. The computation uses two buffers, each consisting of five 32-bit words, and a sequence of eighty 32-bit words. The words of the first 5-word buffer are labeled A,B,C,D,E. The words of the second 5-word buffer are labeled $H_0 , H_1, H_2 , H_3 , H_4 $. The words of the 80-word sequence are labeled $W_0 , W_l,\ldots , W_{79}$. A single word buffer TEMP is also employed.\par

To generate the message digest, the 16-word blocks $M_1, M_2 , \ldots, M_n$ defined in Section 4 are processed in order. The processing of each involves 80 steps.\par

Before processing any blocks, the ${H_j}$ are initialized as follows: in hex,\par

\hspace{2cm} $H_0 = 67452301$\par
\hspace{2cm} $H_1 = EFCDAB89$\par
\hspace{2cm} $H_2 = 98BADCFE$\par
\hspace{2cm} $H_3 = 10325476$\par
\hspace{2cm} $H_4 = C3D2E1F0$\par

Now $M_1,M_2,\ldots, M_n$ are processed. To process $M_i$ , we proceed as follows:\par
a. Divide $M_i$ into 16 words $W_0 , W_1 , \ldots, W_{15}$ , where $W_0$ is the left-most word.\par
b. For t= 16 to 79 let $W_t= W_{t-3}\ XOR\ W_{t-8}\ XOR\ W_{t-14}\ XOR\ W_{t-16}$\par
c. Let $A=H_0,B=H_1,C=H_2,D=H_3,E=H_4$.\par
d. For t = 0 to 79 do\par
\hspace{2cm} TEMP=$S^5\left( A \right)+f_t\left( B,C,D\right) +E+W_t+K_t $;\par
\hspace{2cm} $E=D;D=C;C=S^{30}\left( B \right) ;B=A;A=TEMP;$\par
e. Let $H_0=H_0+A,H_1=H_1+B,H_2=H_2+C,H_3=H_3+D,H_4=H_4+E.$\par
After processing $M_n$, the message digest is the 160-bit string represented by the 5 words 
\[H_0\ H_1\ H_2\ H_3\ H_4 \]

%(如图\ref{SHA-1}):\\
%\begin{figure}[htbp]
%	\centering
%	\includegraphics[width=0.9\textwidth]{SHA-1PROCESS.png}
%	\caption{SHA-1标准原文中对处理过程的描述\footnote{此描述来自于FIPS PUB 180-1 SECURE HASH STANDARD (1995 APRIL 17)第10页}}
%	\label{SHA-1}
%\end{figure}

\subsubsection{Alternate method of computation}
The above assumes that the sequence $W_0 , ... , W_{79}$ is implemented as an array of eighty 32-bit
words. This is efficient from the standpoint of minimization of execution time, since the
addresses of $W_{t-3} ,\ldots, W_{t-16}$ in step (b) are easily computed. If space is at a premium\footnote{这是早期Intel的一种CPU}, an
alternative is to regard { $W_t$ } as a circular queue, which may be implemented using an array
of sixteen 32-bit words $W[O], \ldots, W[15]$. In this case, in hex let MASK = 000000F. Then
processing of $M_i$ is as follows:\par

a. Divide $M_i$ into 16 words $W[O], ... , W[l5]$, where W[O] is the left-most word.\par

b. Let $A=H_0,B=H_1,C=H_2,D=H_3,E=H_4$.\par

c. For t = 0 to 79 do\par
\hspace{2cm} $s = t \bigwedge MASK;$\par
\hspace{2cm} if ($t\geq 16$)\par
\hspace{4cm} $W[s] = W[\left( s + 13\right) \wedge MASK]\ XOR\ W[\left( s + 8\right)  \wedge MASK]\ XOR\ W[\left( s + 2\right) \wedge MASK]\ XOR\ W[s];$\par
\hspace{2cm} $TEMP = S^5 \left( A\right)  + f_t \left( B,C,D\right)  + E + W[s] + K_t;$\par
\hspace{2cm} $E = D; D = C; C = S^{30} \left( B\right) ; B = A; A= TEMP;$\par


\subsection{SHA-1的破解}
\subsubsection{王小云院士的十年一剑}
以下来自于NIST网址的一个信息\footnote{信息来自于\url{https://csrc.nist.gov/News/2006/NIST-Comments-on-Cryptanalytic-Attacks-on-SHA-1}}。\par

\begin{lstlisting}
NIST Comments on Cryptanalytic Attacks on SHA-1 
April 26, 2006 

In 2005 Prof. Xiaoyun Wang announced a differential attack on the SHA-1 hash function; with her recent improvements, this attack is expected to find a hash collision (two messages with the same hash value) with an estimated work of 263 operations, rather than the ideal 280 operations that should be required for SHA-1 or any good 160-bit hash function. This is a very large computation, and to our knowledge nobody has yet verified Prof. Wong’s method by finding a SHA-1 collision, but 263 operations is plainly within the realm of feasibility for a high resource attacker. NIST accepts that Prof. Wang has indeed found a practical collision attack on SHA-1.
NIST held a workshop to consider the status of hash functions on Oct. 31-Nov. 1, 2005 and has reviewed the implications of Prof. Wang’s attack. The attack primarily affects some digital signature applications, including timestamping and certificate signing operations, where one party prepares a message for the generation of a digital signature by a second party, and third parties then verify the signature. There are many applications of hash functions, and many do not require strong collision resistance; for example, keyed hash applications, such as the Hash-based Message Authentication Code (HMAC) or key derivation applications of hash functions do not seem to be affected.
Several steps are now prudent. The first of these is to transition rapidly to the stronger “SHA-2” family of hash functions (SHA-224, SHA-256, SHA-384 and SHA-512) for digital signature applications. The SHA-2 hash functions are in the same general family of hash functions as SHA-1. They could potentially be attacked with similar techniques, but they are much stronger than SHA-1. Practical SHA-2 attacks are unlikely in the next decade; and might never be found, except through decades of exponential growth of available computing power. The SHA-2 hash functions are well along in the commercial system deployment process and are available in many newer systems and applications, but are not yet available in the majority of deployed systems. The primary constraint on the current use of the SHA-2 hash functions for signatures is interoperability; many relying party systems do not yet implement them, and may not do so for several more years. NIST encourages a rapid adoption of the SHA-2 hash functions for digital signatures, and, in any event, Federal agencies must stop relying on digital signatures that are generated using SHA-1 by the end of 2010.
The second step is to encourage hash function research to better understand hash function design and attacks in preparation for selecting additional hash functions. The cryptographic community is in a period of rapid development in the theory of hash functions and their cryptanalysis. NIST plans to host additional hash function workshops; the next of these will be held on Aug. 24-25, 2006 in Santa Barbara, California to follow immediately after the Crypto 2006 Conference.
The third step will be a hash function competition, similar to the successful Advanced Encryption Standard (AES) development and selection process. The schedule for this competition has not yet been determined, but presupposes a sense of sufficient maturity and stability in hash function theory and technology, that the results will improve on or otherwise complement the SHA-2 hash functions, and will occur before the current hash functions are determined to be insecure. NIST does not have strong preconceptions about the number of new hash functions to be selected from this competition, since the very broad range of hash function applications may argue for two or more specialized hash functions.
Lily Chen
NIST
Manager, Cryptographic Technology Group
301-975-6974
\end{lstlisting}

\subsubsection{进一步崩盘}
其实从找到一个碰撞到能够把这个漏洞应用，这之间还是有一定距离的，但是如果找到了碰撞，就是证明其已经不安全，也许很早以前就有人已经开始利用他了，或者把他做为一种能力握到手里。\par
下面是2017年发的另外一个SHA-1不安全的信息\footnote{信息来自于网址\url{https://csrc.nist.gov/News/2017/Research-Results-on-SHA-1-Collisions}}。\par
\begin{lstlisting}
Research Results on SHA-1 Collisions 
February 24, 2017 

On Thursday, February 23rd, Google announced  that a team of researchers from the CWI Institute in Amsterdam and Google have successfully demonstrated an attack on the SHA-1 hash algorithm by creating two files that hash to the same value. 
Their results further emphasize the need to migrate to stronger hash algorithms for digital signatures and other applications that require collision resistance. 
NIST deprecated the use of SHA-1 in 2011  and disallowed its use for digital signatures at the end of 2013, based on both the Wang, et. al, attack and the potential for brute-force attack.  To ensure that practitioners have secure and efficient hash algorithms to provide long-term security, NIST organized an international competition to select a new hash algorithm standard, SHA-3, which is specified in FIPS 202.
Government and industry have made great strides to migrate from SHA-1 to the stronger hash algorithms in the SHA-2 and SHA-3 families.  Those who have not done so yet should migrate as soon as possible.
The work by the CWI-Google team is the culmination of over a decade of research into the SHA-1 algorithm, beginning with the groundbreaking paper by Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu in 2005  that described the first cryptanalytic techniques capable of finding collisions with much less work than brute force.  Cryptographers around the world continued to improve upon these techniques.  The techniques used by this attack were developed by Marc Stevens, one of the members of the joint CWI-Google team.
While all of these researchers have made substantial contributions to the field of cryptography, today we recognize the work by these Google-CWI team members who made the challenging jump from theory to a practical demonstration of an attack:
Marc Stevens (CWI Amsterdam), Elie Bursztein (Google), Pierre Karpman (CWI Amsterdam), Ange Albertini (Google), Yarik Markov (Google), Alex Petit Bianco (Google), Clement Baisse (Google)
The research team has posted additional information at Shattered.io.
\end{lstlisting}
